package class34;

import java.util.Arrays;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MinPatches {

    public static int minPatches(int[] arr, int K) {
        int patches = 0;//缺多少个数字
        long range = 0;//已经完成1~range的目标
        Arrays.sort(arr);
        for (int i = 0; i != arr.length; i++) {
            while (arr[i] > range + 1) {//arr[i] 1 ~arr[i]-1
                range += range + 1;//range+1是缺的数字
                patches++;
                if (range >= K) {
                    return patches;
                }
            }
            range += arr[i];
            if (range >= K) {
                return patches;
            }
        }
        while (K >= range + 1) {
            range += range + 1;
            patches++;
        }
        return patches;
    }

    public static int minPatches2(int[] arr, int K) {
        int patches = 0;//缺多少个数字
        int range = 0;//已经完成1~range的目标
        Arrays.sort(arr);
        for (int i = 0; i != arr.length; i++) {
            while (arr[i] > range + 1) {//arr[i] 1 ~arr[i]-1
                if (range > Integer.MAX_VALUE - range - 1) {
                    return patches + 1;
                }
                range += range + 1;//range+1是缺的数字
                patches++;
                if (range >= K) {
                    return patches;
                }
            }
            if (range > Integer.MAX_VALUE - arr[i]) {
                return patches;
            }
            range += arr[i];
            if (range >= K) {
                return patches;
            }
        }
        while (K >= range + 1) {
            if (K == range && K == Integer.MAX_VALUE) {
                return patches;
            }
            if (range > Integer.MAX_VALUE - range - 1) {
                return patches + 1;
            }
            range += range + 1;
            patches++;
        }
        return patches;
    }

    public static void main(String[] args) {
        int[] test = {1, 2, 31, 33};
        int n = 2147483647;
        System.out.println(minPatches(test, n));
        System.out.println(minPatches2(test, n));
    }
}
